#归并排序

def MergeSort(List):
    def _sort(L, R, List):
        if L != R:
            mid = (L+R) // 2
            _sort(L, mid, List)
            _sort(mid+1, R, List)
            i = L; j = mid+1
            s = []
            while i <= mid and j <= R:
                if List[i] < List[j]:
                    s.append(List[i]); i += 1
                else:
                    s.append(List[j]); j += 1
            while i <= mid:
                s.append(List[i]); i += 1
            while j <= R:
                s.append(List[j]); j += 1
            for i in range(len(s)):
                List[L+i] = s[i]
    _sort(0, len(List)-1, List)

# a=[7,8,6,9,5,3,0,3,9,65,34,2,7,5]
# MergeSort(a)
# print(a)
